Problem statement: zenit17ckf

Fuj, zas ten biely hnus

Počet bodov: 25, časový limit: 1000ms

Zase sneží! Peťo už ani nechce vychádzať z domu. Musí sa vždy naobliekať, vychystať… O to horšie, keď to neodhadne a potom mu je príliš teplo alebo zima. Prišiel teda na spôsob, ako odhadnúť počasie vonku na základe veľkosti snehových vločiek. Nechce sa mu však stále pozerať z okna, tak sa rozhodol to zautomatizovať. Fotoaparát zosníma okno a softvér určí, aká najväčšia vločka sa vonku nachádza. Fotoaparát má, teraz už len ten softvér…

Úloha

Snehová vločka je osemsmerová hviezda zložená z ľadu. Všetky lúče vločky majú rovnakú dĺžku. Veľkosť hviezdičky určíme ako dĺžku jedného lúča.

Zistite, aká najväčšia vločka sa môže nachádzať v obrázku.

Vstup a výstup

Na prvom riadku vstupu dostanete dve čísla \(r\) a \(s\) (\(1 \leq r, s \leq 2000\)) Každý z nasledujúcich \(r\) riadkov obsahuje \(s\) znakov – snímku okna s rozmermi \(r \times s\). Prázdne miesto je značené . a ľad je znázornený znakom #. Vločka má stred a \(8\) rovnako dlhých ľadových ramien, ktoré z neho vychádzajú do všetkých smerov.

Na výstup vypíšte dĺžku ramena najväčšej vločky¹. Ak vonku vôbec nesneží, vypíšte \(-1\).

Časový limit je pomerne prísny. Nevieme zaručiť, že v každom jazyku existuje riešenie, ktoré zvládne vyriešiť každý vstup v časovom limite.

 Príklad

Input:

5 5
#.#.#
.###.
#####
.###.
#.#.#

Output:

2

Input:

3 4
....
.##.
.##.

Output:

0

Sú tu štyri vločky veľkosti 0.

Input:

3 4
....
....
....

Output:

-1

Vonku nie sú žiadne vločky